package pers.tz.题目.leetcode.链表;

import pers.tz.common.ListNode;
import pers.tz.common.ListUtils;

/**
 * @author irony
 * @date 2024-03-12
 */
public class 面试题_02_05_链表求和 {
// 给定两个用链表表示的整数，每个节点包含一个数位。
//
//这些数位是反向存放的，也就是个位排在链表首部。
//
//编写函数对这两个整数求和，并用链表形式返回结果。
// 示例：
//
//输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
//输出：2 -> 1 -> 9，即912
//进阶：思考一下，假设这些数位是正向存放的，又该如何解决呢?
//
//示例：
//
//输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
//输出：9 -> 1 -> 2，即912

    public static void main(String[] args) {
        ListNode l1 = ListUtils.generateList(1, 9, 9);
        ListNode l2 = ListUtils.generateList(1, 1, 1);
        ListUtils.printList(l1, l2);

        ListUtils.printList(addTwoNumbers(l1, l2));
    }

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 先找到长链表和短链表
        int l1Len = getListLen(l1);
        int l2Len = getListLen(l2);

        ListNode l = l1Len > l2Len ? l1 : l2;
        ListNode s = l1Len > l2Len ? l2 : l1;

        // 进位信息
        int carry = 0;
        int curNum = 0;

        ListNode lastNode = null;
        ListNode resHead = l;

        while (s != null) {
            curNum = l.val + s.val + carry;
            carry = curNum / 10;
            curNum %= 10;

            l.val = curNum;

            lastNode = l; // 长短链表长度一致的情况
            l = l.next;
            s = s.next;
        }

        while (l != null) {
            curNum = l.val + carry;
            carry = curNum / 10;
            curNum %= 10;

            l.val = curNum;

            lastNode = l;
            l = l.next;
        }

        if (carry != 0) {
            lastNode.next = new ListNode(carry);
        }

        return resHead;
    }

    private static int getListLen(ListNode listNode) {
        int res = 0;

        while (listNode != null) {
            res++;
            listNode = listNode.next;
        }

        return res;
    }
}
